I am interested in discrete structures and in how we represent and understand them. Four questions guide how I explore a problem:
RepresentationHow can a structure be expressed as simply as possible?
PropertiesWhat properties does the structure exhibit?
ProofHow can those properties be proved?
RefinementWithout adding assumptions, what further properties does the representation reveal, and how might they suggest a better representation?
01
Random graphs · Connectivity · Percolation
Sequence graphs
An edit can define a possible connection between two strings. The success probabilities of those connections shape which strings remain reachable.
A finite prefix-graph illustration
Probability and connectivity.
The vertices are all 15 strings over {a, b} of length at most three, including the empty string ε. Two strings may connect when one is a prefix of the other: append or remove h symbols at the end.
For this illustration, a candidate edge spanning h symbols survives with probability ph = αh. Each edge has its own random draw, including long edges. Select a starting string to see its reachable set.
One sample, held fixed while α changes
Assign each of the 34 candidate edges a separate uniform draw U, then retain it exactly when U < αh. The seeded pseudorandom draws stay fixed while you move the slider or select a vertex. Only Resample generates new draws.
Once the draws and α are fixed, the retained graph and its reachable sets are deterministic. Increasing α can add edges and merge components; it cannot remove a retained edge. A long edge is sampled independently, rather than requiring every shorter edge along its prefix chain to survive.
A finite, 15-vertex realization of independent edge retention with an illustrative probability schedule. It does not establish a critical threshold or prove a phase transition.
Successful connections → reachable stringsFinite random graph
The full prefix graph has 15 vertices and 34 possible edges. At α = 0, every vertex is isolated; at α = 1, all vertices are connected.
Solid: retained edges. Faint dashed: absent edges. Double-ring nodes belong to the selected reachable set; ◆ marks its starting string.
Retained edges
—
Components
—
Largest component
—
Reachable from ε
Enable JavaScript to sample the graph.
Use the same edge draws to compare different values of α.
Path representations: two supporting examples
The views below represent strings as ordered lattice paths. Their middle-deletion operation differs from the terminal edits used in the prefix graph above; the two constructions are not the same graph model.
Example 1
Same endpoint. Different strings.
Start at (0, 0). Read a as one step to the right and b as one step up. Every string traces a complete, ordered path through nonnegative integer coordinates.
Both ab and ba end at (1, 1). Switch between the endpoint and the full path to see what is lost.
Why does the full path preserve the string?
Read each unit step in order: a horizontal step gives a, and a vertical step gives b. This recovers the original string uniquely. An endpoint records only the number of each letter.
This correspondence represents individual strings as ordered paths starting at the origin.
The full path records the order of the steps. Both strings have the same endpoint.
Example 2
Delete a letter. Reconnect the path.
Deleting a symbol removes its corresponding step. The entire suffix then shifts by the negative of that step, so it reconnects to the end of the prefix. The remaining steps keep their order.
In aab, deleting either the first or second a gives ab. In aba, deleting the middle b gives aa.
Why translate the whole suffix?
Every point after the deleted step includes that step in its cumulative displacement. Subtracting the same step vector from all those points removes its contribution while preserving every later step and its order.
Different deletion positions can therefore produce the same resulting string and the same resulting path.
Deleting either a in aab gives ab. Deleting the middle b in aba gives aa. Remove the chosen step, then translate the suffix to reconnect it.
aabOrdered string
Try the first two characters. Different deletion positions can give the same result.
Dashed: original path. Solid: remaining path. The selected step is highlighted before it is removed.
02
Coding theory · Deletion channels · List decoding
Deletion codes
A two-word codebook
Deletion ambiguity.
Repeated deletion positions can give the same output. A different question appears when different original strings give the same output: which one was sent?
Choose two distinct four-bit codewords. Delete exactly one bit from each, keeping every distinct three-bit result once. Select a received string to see its possible originals.
When is this codebook uniquely decodable?
After exactly one deletion, these two codewords are uniquely decodable if and only if their deletion-output sets are disjoint. A shared output has two possible originals. A single unambiguous output is not enough: the maximum below checks every possible received string.
This codebook contains only two words, so its largest candidate list is at most two.
A finite illustration of decoding ambiguity, not a proof of the paper’s general bounds or code-rate guarantees.
Sparseness alone does not specify what to preserve. Even with the same edge budget, different choices can retain or destroy a property of the original graph.
A connectivity example
Two triangles, one bridge.
The original graph has six vertices and seven edges. Compare two choices that each keep all vertices and retain five edges.
Choose a topology, then compare two equally sparse subgraphs. The selected edges decide whether connectivity survives.
A short proof for the selected graph
The connected choice contains the path A–B–C–D–E–F, which visits all six vertices. The disconnected choice omits C–D, the only edge between {A, B, C} and {D, E, F}. Each side stays connected, so there are exactly two components.
These illustrative toy examples isolate connectivity. They are not algorithms or experimental results from the papers below.
A domain-independent design combining contract-net-inspired team formation with session blackboards. A session groups participating agents; its blackboard holds the discussion.
Select an agent to explore the visibility rule: speech memory from sessions they joined, and summaries from other sessions. Select a session to inspect its members and example records.
Two different kinds of relationship
The diagram is a hypergraph: agents are vertices and sessions are overlapping hyperedges.
Membership describes who participates. Information flow describes which records are visible. Here S1 = {A, B} and S2 = {B, C}; B is a single agent shared by both sessions.
The flow view illustrates the intended design, with invented example records. It does not run agents or models, and does not represent a completed bidding, award, or summary-routing implementation.
Agents and session blackboardsDesign illustration · no live agents
S1 contains A and B. S2 contains B and C. B is one shared agent. Participants retain session speech memory; other agents can see a session summary.
Agent B participates in S1 and S2.
Regions show session membership; each session has its own blackboard.
05
Data mining · Visual representation · Pattern discovery
Finding structure in noisy data
A data-mining course exploration
Change the representation. Look for recurring structure.
This course project explored how a change of representation could expose structure in messy data. Trajectories become an image; alpha compositing makes repeated spatial patterns easier to see.
Here, the input consists only of raw trajectory coordinates. Their accumulated footprints reveal recurring shapes, while ideas from computer vision suggest further geometric analysis. No road map or transport network is supplied.
From trajectories to color and coverage
Each trajectory produces a binary footprint on a fine spatial grid. A cell is covered when its center lies within the chosen stroke radius of the trajectory. Repeated visits within one trajectory still count once.
If n trajectories cover a cell, a zero-valued ink channel over white at opacity a gives q = (1 − a)n. We read red for blue ink and green for red ink, then invert n = log(q) / log(1 − a) before rounding and thresholding.
Inspection uses unrounded model values at cell centers. Raw strokes are antialiased for display; accumulation and candidate decisions use the binary model footprints. Finite image color precision can limit inversion from a saved image.
What remains uncertain?
A compact crossing hotspot and an extended narrow region can both pass a density threshold. This stage retains candidate areas for further shape analysis. It does not prove a road or metro line exists, determine transport type, or reconstruct a network.
The representation also loses journey identities, direction, order, and exact sequence support. All traces here are synthetic, not real people’s data.
Proposed geometric next step
Hough line extraction → candidate corridors
Not implemented in the original project or this illustration.
Raw traces → image → candidate areasSynthetic trajectory data
Continuous raw trajectories on a blank field. No network is provided.
Inspect a sample point High coverage
Click a point in the image, or choose a sample.
Distinct trajectories n
—
Red channel q
—
Model inverse
—
The crosshair marks the sampled model cell. Candidate areas are not classified or fitted lines.
Enable the interactive example to inspect the spatial accumulation.
06
Random graph generation · Preferential attachment · Degree distributions
A network growing one node at a time
Simulated Barabási–Albert model
Who gets the next edge?
Each new node connects to m distinct older nodes. An eligible node is selected with probability proportional to its degree; after selection, it is removed from that step’s candidate set.
Step through the growth or play the simulation. The degree histogram updates with the network.
Seed, sampling, and limits
The seed is a connected four-node cycle. A fixed pseudorandom seed makes each choice of m reproducible. Selection uses pre-step degrees, renormalized over eligible older nodes, without replacement. The graph stays simple and connected, with a maximum of 80 nodes.
This is a simulated BA-style preferential-attachment model. It is not a reconstruction of DBLP or evidence that a real network follows a power law. Node positions are illustrative; node size reflects degree.
Preferential attachment in motionSimulated BA model
Changing m restarts this seeded simulation.
The seed is a four-node cycle. Each new node attaches to m different older nodes, sampled proportionally to degree.
Nodes 4 / 80Edges 4Max degree 2
Degree histogram degree → number of nodes
Ready. Four-node cycle seed; m = 2. Use Step or Play to add nodes.
The newest node and its edges are highlighted. Playback pauses when the page is hidden.
These small examples illustrate questions I like to explore.
