Home
Graphs, designs, numbers, etc.'s Journal
 
 [Most Recent Entries] [Calendar View] [Friends]

Below are the 20 most recent journal entries recorded in Graphs, designs, numbers, etc.'s LiveJournal:

    [ << Previous 20 ]
    Monday, May 19th, 2008
    4:23 pm
    [sclark223]
    tentative DANGER weekend
    Upcoming DANGER: How does the weekend of July 11 (Friday) thru July 13 (by default, Sunday) suit everyone? Located at Huntingdon College, in Montgomery AL? I'll send email too, to the usual folks who may not blog here. If most folks find this weekend acceptable, then I'll work on specifics - maybe even a website, [info]alexsala! :)
    Friday, April 25th, 2008
    9:30 am
    [trimmje]
    Let's Make a Deal v. Deal or No Deal
    So at knit night last night, a discussion came up of the Monty Hall problem and Deal or No Deal, and whether thousands of people are getting misled about probability every week by Howie Mandel. (Indeed, my knitting group rocks mightily.)

    Monty Hall asks you to pick one door of three, one has a car behind it, two have goats. Once you have chosen, a non-chosen door is opened to reveal a goat, and despite the un-intuitiveness of it, you still only have a one in three chance of having the car.

    Deal or No Deal claims at each level that if a person has chosen a case and there are n-1 cases left to be opened and the million dollar prize hasn't appeared yet, there is a one in n chance that the million dollar prize is in the Chosen Case. Open k more cases without revealing a million dollars, and there's now a one in n-k chance for the Chosen Case.

    My argument is that the difference between these two situations is that in Deal or No Deal the contestant chooses which cases to open, and so there is the possibility of opening case K with a million dollars - eliminating the possibility that the Chosen Case has the million. In Monty Hall, on the other hand, the people opening the door have perfect information, and so when they open a door it's always a goat. This means that a door is opened in any of the three configurations of two goats and a car, but the information given doesn't actually eliminate any possibilities.

    I'm just wondering if I'm on the right track here or if a new configuration of Monty Hall has gotten past my instincts again.
    Thursday, February 28th, 2008
    2:51 pm
    [leachboy]
    bitstrings!
    The book I'm using to teach combinatorics poses the following problem:

    How many binary sequences of length 18 are there that start with a run of 1s, that is, a consecutive sequence of at least one 1, then a run of 0s, then a run of 1s, then a run of 0s, and such that one run of 1s has length at least 8.

    They claim that the answer is 240, but I think that it's 239. What do youse guys think?
    Thursday, January 31st, 2008
    5:08 pm
    [gaffetheorist]
    Filling out travel forms
    My conference plan for the next six months:
    * Boca, March 5th-7th. (Missing the first two days.)
    * Mathematical Abundance at Illinois State, April 18th-19th.
    * MIGHTY 46 at WVU, April 25th-26th.
    * Istanbul, June 16th-20th.
    * DANGER '08, apparently in Montgomery, sometime in July?

    What am I missing?
    Monday, December 10th, 2007
    3:33 pm
    [gaffetheorist]
    Fun facts about the golden ratio
    Let φ denote the Golden Ratio: φ = (1 + √5)/2.

    Fact #1: Every positive integer can be expressed as a sum of distinct integer powers of φ.

    Fact #2: If you require that one never employs consecutive powers of φ, then the representation is unique.

    (I'm pretty sure that this can be refined as follows: take any finite linear combination of powers of φ using positive integer coefficients. Then the resulting number can be expressed uniquely as such a linear combination using only the coefficients 0 and 1.)

    Question: What positive real numbers share Fact #1 with φ? 1 and 2 both fit the bill, though somewhat boringly in both cases; these represent the extremes, in that any number larger than 2 will perforce miss 2, and for any number smaller than 1 we can just consider the reciprocal instead. Instructive, I think, is that φ satisfies the equation φ = φ0+φ-1; the corresponding equations for 1 and 2 are 1 = 10 and 2 = 20+2-1+2-2+… Do all positive reals that satisfy versions of this (effectively, truncations of the Laurent series for 2) also satisfy Fact #1? Are there other reals that do?

    Also: can anything interesting be said about the set of numbers that admit these representations in terms of φ?
    Saturday, October 20th, 2007
    9:55 am
    [sclark223]
    Curt's Turks?
    So who is planning to go to Turkey this June? Sule says "everybody" will be there - I have never been sure who she meant by that.
    Saturday, September 22nd, 2007
    2:15 am
    [gaffetheorist]
    Steiner systems
    Anyone know whether a (3,5,50) Steiner system (AKA a 3-(50,5,1) design) exists? And/or where I might find it? The various combinatorial object generators I know of don't seem to do much with block designs.
    Sunday, January 28th, 2007
    1:40 pm
    [alexsala]
    Domination 101
    I'm scheduled to give a 45 minute talk tomorrow on domination. I've got about 30 minutes of material. HELP!
    11:09 am
    [alexsala]
    Anybody wanna have a DANGER party at the SE-MAA the week after Boca? I'm taking a Jeopardy team to the conference, and I need something to unwind without turning my brain off - I'll buy beer if people will come play math with me. Oh, and I'm looking for a roommate for it too. MAA page
    Saturday, January 27th, 2007
    11:59 pm
    [trimmje]
    Boca 2007 again
    So I'm thinking of going for some portion of the week, contingent on having a reasonably-priced place to stay - i.e., probably a roommate or so who would be willing to share costs.  I'm clean, housetrained, and I've been told my snoring is soft and cute. 

    Anyone?  Bueller? 
    Wednesday, January 17th, 2007
    2:15 pm
    [leachboy]
    Boca 2007
    I'm trying to make my plans for Boca this year. I plan to attend the conference Monday through Wednesday, and possibly a few hours on Thursday morning before flying back to the ATL. I'm sharing a room with Abi at the motel formerly known as the Ramadan. What is still up in the air is when I will fly down. Abi's flying down on Saturday, and I might do the same, although if no one else will be there that day, I might opt to wait until Sunday.

    Are any of the rest of you planning to arrive on Saturday?

    UPDATE: It's official. I'm flying into Fort Lauderdale on Saturday at 3:50 PM and flying out on Thursday at 12:40 PM.
    Tuesday, October 24th, 2006
    3:53 pm
    [gaffetheorist]
    Regular graphs with a given substructure
    At least the first of these questions has probably been tackled someplace; look familiar to anyone?

    (1) Let G be a graph with δ(G)<Δ(G); must there exist a regular graph H which contains G as an induced subgraph? Assuming so, find a construction for such an H that minimizes... something. (Vertex degree? Number of vertices? Number of edges? Not sure which is the more interesting question, but you can get different answers.)

    (2) As above, but now require that H be vertex-transitive.

    (3) As in (1), but now require that the automorphism group of G extend to the automorphism group of H. (N.B. I mean something stronger than having Aut(G) be a subgroup of Aut(H); every automorphism of G should be extendable to an automorphism of H.) This could also be combined with (2), though it doesn't need to be.

    Current Music: Sloan
    Tuesday, August 8th, 2006
    4:41 pm
    [gaffetheorist]
    Too lazy to look this up...
    ...but it seems like something that should be known, and thus that some of you might know.

    Can every balanced tournament on 2n+1 vertices ("balanced" here meaning that indegrees = outdegree) be decomposed into directed Hamilton circuits?
    Friday, July 7th, 2006
    2:06 pm
    [gaffetheorist]
    Geometry of chords
    OK, so this is pretty neat: a professor of music at Princeton's come up with a topological model for voice-leading which illustrates why some chord transitions sound better than others, and specifically why people like Chopin could do things that fly in the face of the "rules of harmony" and still sound pretty amazing.

    The original article is on the author's webpage, and it seems like pretty serious stuff. My differential geometry and topology are sadly lacking, so I'm still bogged down in the definitions; when he talks about using the orbifold Tn/Sn as a model for n-note chords, I know what that is but I don't know what it looks like, you know?
    Friday, June 30th, 2006
    4:17 pm
    [gaffetheorist]
    Eulerian round-robins again
    I feel like returning to a previous theme. This is a problem I tossed about a couple of years ago, and then I proceeded to not really think about it much. Maybe Take 2 will go better.

    The setting: suppose you're running a round-robin tournament and you've only got a single pitch to work with. For simplicity's sake, you want consecutive matches to have a player in common; however, you never want to someone to play three matches in a row. You can model this with an Euler tour of Kn, where n = the number of players and each edge corresponds to the match between the incident players/vertices. (Assume that n is odd, so that such a tour actually exists.)

    After you (as a player) have been in a pair of matches, ideally you'd like to have some time to rest: the more time (intervening matches) between your appearances on the pitch, the better as far as you're concerned. How can we best ensure resaonable gaps for all players?

    (If you don't like the tournament setting, because you think it's unrealistic, another possible setting might be in a networking environment: imagine something like a token-ring system, except instead of a ring the token is being passed along a clique to ensure that direct universal connectivity exists. You don't want a server in this network to receive the token too soon after having sent it out. I don't know whether that's any more realistic, but it's different.)

    If you try this with a small example --- say n=5 --- it seems like you always have to pull a "short turn" somewhere: for some vertex A, there's only a single intermediate match between one appearance of A and the next. (Possibly I just haven't looked hard enough for a counterexample, though.) Pursuing this idea, let f(n) denote the maximum size of a smallest "gap" between a vertex's appearances in a tour, the max being taken over all tours. So what can we say about f(n)? I'd imagine that it's linear in n --- I'd be surprised if it grew any slower than that, but that's just instinctive without any real backing. And is f(n) really the best way to evaluate a tour/schedule from the point of view of player rest? Would it be better to try and equalize the list of all gaps, or would that best be done by maximizing the size of a smallest gap?

    Current Music: Stadium Arcadium
    Sunday, April 16th, 2006
    8:25 pm
    [leachboy]
    WikiSurveys?
    A comment on Slashdot gave me an idea. It can be tough sometimes to figure out what is known and what is not known in a particular area, especially when terminology isn't consistent between authors. We usually use MathSciNet to try to find what's known, but that's less than ideal because each entry in their database is a publication. If an author proves an intermediate result that isn't reflected by the title or abstract, it can be really tough to find.

    Here's the idea: We create a new database where each item is a lemma or a theorem, and have fields that reference the publication, author, etc. The database could be maintained by the community the same way wikipedia is, only we may want to restrict editorial privileges to keep out vandals and crackpots. Basically, the database would be a community-maintained survey paper, so it would probably be best to have a separate wiki for each broad topic (i.e. domination, decompositions, etc.)

    To start such a project, the work required would be roughly that of writing a survey paper plus setting up a webserver. To keep it going and useful, we'd need for it to become the go-to place for people working in that area, and somehow convince people to add their results after they are published.

    What do you guys think? Could something like this catch on? If so, would anyone want to consider applying for funding for such a project?
    Tuesday, April 4th, 2006
    5:50 pm
    [gaffetheorist]
    Mediated relationships in social networks
    Suppose you've got a graph which represents a social network: each vertex is an individual within the network, and an edge between two vertices represents a relationship between the corresponding individuals. Relationships can vary in strength, and can also be positive or negative, and so to each edge we'll assign a weight from [-1,1], where -1 represents strong antipathy between the two individuals and 1 strong sympathy, with 0 representing neutrality or ambivalence. (But known neutrality, as opposed to the lack of an edge; the latter would denote two individuals with no direct contacts to each other.)

    ( Some speculation on what you could do with this )

    None of this is terrifically well-formed as far as thoughts go, and before I go much further I might should talk to someone in Soc or Anth to find out about, you know, reality. But if anyone wants to brainstorm, feel free.

    (PS. LJ spellcheck rejects "vertices" in favour of "vertexes". The horror!)
    Wednesday, February 8th, 2006
    6:44 pm
    [gaffetheorist]
    +/- designs
    Let G, H, and X be simple graphs. A (G+/H-) decomposition of X is a family of graphs {G1, G2, ..., Gp, H1, H2, ..., Hq} with the following properties:
    1. Each Gi is isomorphic to G, each Hj is isomorphic to H.
    2. If Z is a simple graph and v,w are vertices, define the function ev,w(Z) to be 1 if vw is an edge of Z and 0 otherwise. Then for every pair of vertices v,w, we require that ev,w(X)=[Σev,w(Gi)] - [Σev,w(Hj)], where the sums are taken over i=1...p and j=1...q.
    In other words: we can produce X by assembling enough copies of G, and then subtracting off enough copies of H.

    As an example, we can find a (K3+/K3-) decomposition of C6: let {a,b,c,d,e,f} be vertices of C6 in cyclic order, and take {a,b,c}, {c,d,e}, and {a,e,f} for our "positive" triangles and {a,c,e} as a "negative" triangle to remove the extra edges.

    There are some natural extra constraints that we might want to add in: for instance, we might require that -- as happens in the example -- the result of assembling the copies of G gives a simple graph (i.e. no "positive padding", with parallel edges being constructed and then subtracted away). Contrariwise, we might require that every one of the subgraphs Gi and Hj be a subgraph of X (i.e. no "negative padding" where non-X edges get added and then removed).

    One obvious necessary condition (for the original problem and any constrained version of it) should be that the number of edges in X should be a multiple of the GCD of the edge-counts of G and H.

    It seems to me like there should be some connections with embedding to be had here, but I don't know what they are.

    As an initial problem to think about: can we characterize those graphs which admit (K3+/K3-) decompositions?
    Tuesday, January 17th, 2006
    3:14 pm
    [gaffetheorist]
    Boca planning -- roll call
    Who all's looking to go to Boca this year?
    Saturday, December 3rd, 2005
    4:43 pm
    [gaffetheorist]
    Graph theory and circuitboards
    We're going through a bird's-eye view of graph theory in my intermediate discrete class right now. The other day I was showing them planar graphs and mentioning some of the basic results regarding them, and one of my students asked me the following question: Suppose you have a circuit to etch into circuitboards. Since not all graphs are planar, there will be some circuits that you can't lay onto a single board. Is there a way to figure out how many boards you'll need for a given circuit?

    My first thought is that you shouldn't ever need more than two, but I have no justification for that at all. To some extent the answer to the real-world question is going to depend on geometric concerns about the size of the circuitboard vs. the width of a segment of the circuit. Leaving that aside, though, and assuming that a circuitboard can be arbitrarily large: can the crossings in a non-planar graph always be arranged so that only two layers are sufficient? Or would the genus of a given graph play some role in determining how you could stack its corresponding circuit? Have any of you seen this problem, or something like it, before?
[ << Previous 20 ]
About LiveJournal.com